Because each node of a packet network typically receives packets from a multiplicity of other nodes and must re-direct these packets to a multiplicity of destinations (i.e. other nodes), the nodes of a network must be equipped with means for accomplishing such receipt and re-direct. Furthermore, because traffic in a network flows constantly, such means must be capable of performing both the receipt and the re-direct functions simultaneously.
The receiving and re-directing functions required of a node (also known together as the routing functions) are performed by a device called a switch. As each node has a multiplicity of input and output links, the prime purpose of the switch is to route incoming packets arriving on a particular input link to the proper output link. A number of different techniques have been proposed for carrying out the switching (routing) function. The present invention is concerned with improving one of these techniques, the technique known as shared memory.
A shared memory switch consists of a single memory having multiple input and output lines. FIG. 1 depicts schematically a typical shared memory switch 10, in which the input lines of the switch, denoted generally as 12, are all connected to a single input port 14, and the output lines, denoted generally as 16, are connected to a single output port 18. It will be appreciated that although in FIG. 1 N input lines and N output lines are depicted, the number of input and output lines need not be equal. At given time intervals, packets arriving on the input lines (the first packet on each line at each time interval) are multiplexed into a single stream which is then fed through the single input port into the memory for storage. Once inside the memory, packets are organized into separate output queues, one queue for each output line. The processes and apparatus controlling the storage of packets and their organization into queues are depicted schematically in FIG. 1 as controller 20, which controls the writing of multiplexed packets into the memory (WA) and the reading of multiplexed packets from the memory (RA). To send packets to their correct destinations, the process is reversed: at each time interval, an output stream of packets is formed by sequentially retrieving packets from the output queues (the first packet in each queue at each time interval), and this output stream is then de-multiplexed and the packets transmitted on the output lines. The multiplexing and de-multiplexing of packets is depicted schematically in FIG. 1 as S/P (serial-to-parallel) and P/S (parallel to serial) respectively.
In practice, at any given time a shared memory switch is engaged in all of the input and output processes (multiplexing, storing, organizing into queues and de-multiplexing): at set time intervals, packets at the heads of non-empty queues are sent to the corresponding output link, and incoming packets are sent to their assigned queues. For purposes of discussion throughout the remainder of this patent application, the Applicants will relate to input and output lines of the shared memory switch as if these lines were connected directly to the switch and the multiplexing/de-multiplexing step was unnecessary.
Because multiple cells arriving at the same time on different input lines may be destined for the same output line, switches must also be capable of buffering (sometimes referred to as queuing). While in theory a switch may buffer cells at the input or the output of the switch, in shared memory switches a third possibility is available, viz. to buffer the cells internally. Shared memory switches have gained popularity because, by appropriately controlling the memory read/write, the switching and buffering functions of the shared memory switch may be achieved simultaneously. This feature imparts significant advantages to shared memory switches: such switches do not suffer from throughput degradation (a drop-off in the total number of cells passing through the switch) due to “head-of-line blocking”, a phenomenon inherent in input-buffered switches.
Buffer allocation determines how the total buffer space, i.e. the memory, will be used by individual output lines of the shared memory switch. The buffer allocation is in turned determined by implementation of a buffer management policy. Several such buffer management policies are known in the art. Known buffer management policies are based on a model of a shared memory switch having N output lines (and usually N input lines) and a total buffer space of M equally sized packets. Most of these policies operate on a non-preemptive basis, i.e. once a packet has been queued, it will not be removed from a queue, and therefore these policies involve determining whether an incoming packet will be accepted or rejected. (Packets which have been queued are sent to their destinations on a first-in-first-out (FIFO) basis.) For the sake of completeness, however, it is noted that some buffer management policies have been proposed which follow a preemptive policy. These buffer management policies are known as “push-out” or “drop-on-demand” and variations thereof, and involve “pushing out” an already queued packet under certain conditions. Because the “push-out” step is difficult to implement in practice at the speeds under which modern packet switches must operate, “push-out” and its variants have not been widely adopted commercially.
Of the non-preemptive buffer allocation policies, the two simplest policies are known as complete partitioning and complete sharing. In complete partitioning (CP), the entire buffer space is permanently partitioned among the N output lines. Although in principle each queue could be assigned a different amount of space, in practice under CP each queue is allocated an equal amount of buffer space, M/N packets for each of the N queues. Since the sum of individual output line allocations is equal to the total buffer memory M, complete partitioning does not provide any sharing. This can represented mathematically as follows: let M be the total buffer space (memory) in a shared memory switch having N output lines and N corresponding output queues, let Tq be the buffer space allocated to queue q, and let Lq be the buffer space actually occupied by queue q. In complete partitioning,Lq≦Tq  (1)for all q(q=1 to N) and
                                          ∑                          q              =              1                        N                    ⁢                      T            q                          ≤        M                            (        2        )            
(Implicitly, this also means that the sum of buffer space occupied by all queues cannot exceed the total amount of memory available, i.e.
                                          ∑                          q              =              1                        N                    ⁢                      L            q                          ≤        M                            (        3        )            but this condition is true by definition for the shared memory switch, irrespective of the buffer allocation policy implemented.)
The advantage of complete partitioning is that the determination to accept or reject a packet is easy to make: if the buffer allocation for the queue to which an incoming packet is assigned is already full, the incoming packet is rejected; if the buffer allocation for the queue to which the incoming packet is assigned is not full, the packet is accepted. CP also ensures that the memory is allocated fairly among the output queues. The disadvantage of a complete partitioning policy is that the total memory is often under-utilized, since unused memory from an inactive queue cannot be utilized by a highly active queue temporarily requiring additional memory.
At the other extreme there is the complete sharing (CS) policy, in which all packets destined for all queues are accepted until the memory is completely full. Using the same notation as above, this can be expressed by adherence to condition (3), without adherence to conditions (1) or (2). While complete sharing ensures that the memory space will never be under-utilized (if necessary, the entire buffer space may be used), it also enables a single highly active queue to monopolize the buffer. This is unfair and can be detrimental to performance under some circumstances. For example, if the highly active queue contains packets which are part of an (extremely large) e-mail message, for which a delay of several seconds in transmission will not be critical, and other packets which are part of a real-time voice transmission are consequently rejected by the buffer, the recipient of the voice transmission will receive a garbled transmission. This intuitive insight has been borne out by computer modeling and simulation: under balanced traffic conditions, CS has been shown to outperform CP (in the sense that fewer packets are lost in CS), but under imbalanced traffic conditions, which more closely mimic traffic conditions in actual ISDN networks, CP outperforms CS.
To try to overcome the drawbacks of complete sharing and complete partitioning, but to still take advantage of the benefits of each of these buffer management policies, several hybrid buffer management policies have been proposed. One such policy is known as sharing with maximum queue lengths (SMXQ). In this policy, each output queue is allocated a finite amount of buffer space. Although in principle the allocation for each queue may vary, in practice each queue is typically allocated the same amount of buffer space. In this respect SMXQ is similar to CP. However, unlike in CP, the total buffer allocations may together exceed the total memory space M. Furthermore, unlike in CP (but as in CS), sharing between output queues is allowed. SMXQ can thus be expressed mathematically by adherence to the conditions of equations (1) and (3) above, but the inequality in (2) is reversed to yield condition (2′) which must also be adhered to:
                                          ∑                          q              =              1                        N                    ⁢                      T            q                          ≥        M                            (                  2          ′                )            
The result of these conditions is that no single queue is allowed to monopolize the total buffer space, but by the same token a queue in need of additional space is able to utilize some of the unused space allocated to another queue. The degree of sharing allowed will be determined by the maximum queue length allowed: the closer the maximum queue length is to M/N (or more generally, the closer the total allocation for all queues approaches M), the more closely the policy approaches CP, and the closer the maximum queue length is to M, the more closely the policy approaches CS. Thus in SMXQ the maximum queue length is set as less than M but greater than M/N. Computer modeling and simulation has shown that under imbalanced traffic conditions, SMXQ generally outperforms both CS and CP.
It should be noted that to the best of the inventors' knowledge, there is at present no optimal solution for choosing the degree of sharing under imbalanced traffic conditions. The chief disadvantage of SMXQ is that if a situation arises where there are many active output lines, the total buffer space taken by these active lines may leave some other (lightly loaded) output line with insufficient space. This can be a problem if it is desirable to distinguish between different classes of packets, e.g. real-time voice transmission packets vs. e-mail packets.
Another solution intermediate between CP and CS is known as sharing with minimum allocation (SMA). In SMA, a minimum amount of buffer space is always reserved for each queue. In principle, the amount reserved for each queue may differ, but in practice an equal amount of space is reserved for each queue. The minimum amount Rq reserved for queue q is set as less than M/N (the reservation equivalent to each queue under a CP policy in which all queues receive equal allocations) and greater than 0 (the reservation at which the policy is equivalent to CS). More generally, all queues may be given different non-zero minimum allocations. In mathematical terms, this can be expressed as adherence to conditions (4) and (4′):
                                          ∑                          q              =              1                        N                    ⁢                      max            ⁡                          (                                                L                  q                                ,                                  R                  q                                            )                                      ≤        M                            (        4        )                                                      R            q                    >                      0            ⁢                          :                        ⁢            q                          =                  1          ⁢                                          ⁢          …          ⁢                                          ⁢          N                                    (                  4          ′                )            wherein max(Lq,Rq) refers to the larger of the two values Lq and Rq.
A third solution intermediate between CP and CS, known as sharing with maximum queue and minimum allocation (SMQMA), combines both SMXQ and SMA: a minimum amount of space is allocated for each output queue, but a maximum queue length is also imposed. The guarantee that each output line has a minimum amount of space allocated serves as a simple and convenient method for ensuring that high-priority traffic is allocated buffer space, even in a shared buffer environment. An example of a commercially available shared memory switch employing an SMQMA buffer management policy is the Cisco Lightstream 1010 switch, in which every output line has a fixed reservation for high priority continuous bit rate traffic. The remainder of the buffer space is used in accordance with an SMXQ policy.
SMXQ, SMA and SMQMA all involve static thresholds: they were developed under assumptions of static environments where traffic loads may be imbalanced (i.e. the queues of some output lines may be more heavily loaded than the queues of other output lines) but the overall traffic loads do not change with time. Such assumptions do not reflect the reality of most computer networks, in which overall traffic loads vary significantly over time. This leads to degradation in the performance of shared memory switches when the actual traffic conditions encountered in the network deviate from the nominal values that the switches were designed to accommodate. This has led to attempts to develop buffer management policies which can adapt to changes in network traffic conditions.
One such type of policy has been termed “adaptive control” (see Thareja & Agrawala, IEEE Trans. Commun., vol. COM-32, no. 6, June 1984, pp. 737-740). In this type of policy, the allocation for all output lines is revised in response to changes in traffic conditions. Traffic estimations are made by statistical measurements of incoming traffic, and these are compared to the conditions which existed at the last allocation update. The policy can thus determine when the allocation should next be revised and what the new allocation should be. While the general idea of an adaptive control policy appears useful, in practice it has been difficult to devise particular buffer management policies along these lines. For example, the statistical estimation of network traffic, which it was once thought would prove to be a trivial matter, has proven to be quite complicated. Also, it is much more difficult to determine an optimal allocation for N outputs than for two outputs, as was done by Thareja & Agrawala. Thus adaptive control policies have not been widely adopted.
Another type of policy is known as dynamic threshold (DT) (described in Choudhury et al., IEEE/ACM Trans. Commun. 6(2) April 1998, pp. 130-140). In DT, the queue length thresholds of the output lines are set as proportional to the current amount of unused buffer memory. In mathematical terms,Lq≦αF  (5)for all q from 1 to N, wherein α is a proportionality constant and F is defined as
                    F        =                  M          -                                    ∑                              q                =                1                            N                        ⁢                          L              q                                                          (        6        )            
Packets or cells arriving for a given output line are rejected if the length of the queue for that output line exceeds the current threshold value, i.e. if condition (5) will be violated by acceptance of the incoming packet for queue q. During periods of overall light traffic, this enables some output queues experiencing relatively high activity to utilize most of the buffer space. As overall traffic flow increases and the demand for memory for other queues increases, the queue length threshold decreases, thus forcing heavily loaded queues to unload packets before said heavily loaded queues will be allowed to accept more packets, and enabling previously lightly loaded queues to fill up.
The principal difficulty with the dynamic threshold policy is that the proportionality constant α is set at some value and remains at this value throughout the use of the shared memory switch. However, computer modeling and simulation has shown that while proportionality constants over a range of values produce results which are better than pure CP or pure CS (or, in general, even better than SMXQ), the performance of the DT policy under different conditions differs with the value of the proportionality constant. Consequently, no single proportionality constant can be chosen which performs optimally over all network traffic conditions.
There is thus a need for a buffer management policy which can better optimize the use of the buffer space in a shared memory switch than buffer management policies which are presently known.